package oct2013.linkednode;

public class PartitionList {
	public ListNode partition(ListNode head, int x) {
		ListNode dummy1 = new ListNode(0);
		ListNode dummy2 = new ListNode(0);
		ListNode tail1 = dummy1;
		ListNode tail2 = dummy2;
		ListNode cur = head;
		while (cur != null) {
			if (cur.val < x) {
				tail1.next = cur;
				tail1 = cur;
			} else {
				tail2.next = cur;
				tail2 = cur;
			}
			cur = cur.next;
		}
		tail2.next = null;
		tail1.next = dummy2.next;
		return dummy1.next;
	}
}
